package com.gitee.feizns.explore.data_structure.array.easy;

import java.util.Stack;

/**
 * 581. 最短无序连续子数组
 * @author feizns
 * @since 2020/1/14
 */
public class FindUnsortedSubarray {

    public static void main(String[] args) {
        System.out.println(findUnsortedSubarray(new int[]{ 5, 4, 3, 2, 1, 2 }));
    }

    public static int findUnsortedSubarray(int[] num) {
        int l = -1;
        int r = -1;
        Stack<Integer> stack = new Stack<>();
        stack.push(num[0]);
        int max = num[0];
        for (int i = 1; i < num.length; i++) {
            if ( !stack.isEmpty() ) {
                if ( num[i] < stack.peek() ) {
                    if ( l == -1 )
                        l = i;
                    while ( !stack.isEmpty() && stack.peek() > num[i] ) {
                        l--;
                        stack.pop();
                    }
                } else if ( l == -1 )
                    stack.push(num[i]);
            }
            if ( num[i] < max )
                r = i;
            else
                max = num[i];
        }
        return l == r ? 0 : r - l + 1;
    }

}
